package leetcode.editor.cn;

import java.util.*;

/**
 *
 */
//[1091]二进制矩阵中的最短路径
public class ShortestPathInBinaryMatrix1091{
    public static void main(String[] args) {
//        int i = new ShortestPathInBinaryMatrix1091().new Solution().shortestPathBinaryMatrix(new int[][]{{0, 1}, {1, 0}});
        int i = new ShortestPathInBinaryMatrix1091().new Solution().shortestPathBinaryMatrix(new int[][]{{0, 0, 0}, {1, 1, 0}, {1, 1, 0}});

        System.out.println("ShortestPathInBinaryMatrix1091:main:" + i);
    }

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        int[] dx = {0, 0, -1, 1, -1, 1, -1, 1};
        int[] dy = {-1, 1, 0, 0, -1, -1, 1, 1};


        //代码来自LeetCode国际评论区。
        final int[][] dirs = new int[][]{{0, 1}, {1, 0}, {1, 1}, {0, -1}, {-1, 0}, {-1, -1}, {-1, 1}, {1, -1}};

        public int shortestPathBinaryMatrix(int[][] grid) {
            int n = grid.length;

            //Heuristic based priority Queue- Choose closest to the target
            Queue<int[]> queue = new PriorityQueue<>((a, b) -> {
                if (a[2] != b[2]) {//step a - b.
                    return a[2] - b[2];
                } else {
                    int manhattenDistanceA = (n - 1 - a[0]) + (n - 1 - a[1]);
                    int manhattenDistanceB = (n - 1 - b[0]) + (n - 1 - b[1]);
                    return manhattenDistanceA - manhattenDistanceB;
                }

            });
            //The above queue stores a,b,c where c is the least distance from source

            if (grid[0][0] != 0 || grid[n - 1][n - 1] != 0) return -1;
            if (n == 1) return 1;
            queue.offer(new int[]{0, 0, 1});//step 1,优先级考虑，第几步，
            while (!queue.isEmpty()) {
                int[] current = queue.poll();
                if (grid[current[0]][current[1]] != 0) {
                    continue;
                }
                grid[current[0]][current[1]] = -1; ///Mark the least distant node from source as visited

                for (int[] dir : dirs) {
                    int newX = current[0] + dir[0];
                    int newY = current[1] + dir[1];
                    if (newX >= 0 && newX < n && newY >= 0 && newY < n && grid[newX][newY] == 0) {
                        queue.offer(new int[]{newX, newY, current[2] + 1});//step 走的步数 +1
                    }
                    //Special check to get the end
                    if (newX == n - 1 && newY == n - 1) {
                        return current[2] + 1;
                    }
                }
            }
            return -1; //No path found
        }


        //A* timeout
        // 链接：https://leetcode.cn/problems/shortest-path-in-binary-matrix/solution/bfsa-qi-fa-sou-suo-duo-chong-fang-fa-you-jrqp/
        public int shortestPathBinaryMatrixA(int[][] grid) {
            if (grid == null) return -1;

            int len = grid.length;
            if (grid[0][0] == 1 || grid[len - 1][len - 1] == 1) return -1;
            if (len <= 2) return len;//jian zhi

            boolean[][] visited = new boolean[len][len];

            //默认小顶堆。
            PriorityQueue<Node> deque = new PriorityQueue<>(10, new Comparator<Node>() {
                @Override
                public int compare(Node o1, Node o2) {
                    return Double.compare(o1.cost, o2.cost);
                }
            });
            deque.offer(new Node(0, 0));
            while (!deque.isEmpty()) {
                Node cur = deque.poll();

                if (cur.x == len - 1 && cur.y == len - 1) {
                    return pathLength(cur);
                }
                visited[cur.y][cur.x] = true;

                for (int j = 0; j < dx.length; j++) {
                    if (valid(cur.x + dx[j], cur.y + dy[j], len, grid, visited)) {
                        //double distance = distance(cur.x + dx[j], cur.y + dy[j], len - 1, len - 1);
                        //为什么 +1 ？？？。是因为。优先级相同时，后一步+1 么？应该是的。
                        double distance = cur.cost + 1 + distance(cur.x + dx[j], cur.y + dy[j], len - 1, len - 1);
                        Node node = new Node(cur.x + dx[j], cur.y + dy[j], cur, distance);
                        deque.offer(node);
                    }
                }
            }
            return -1;
        }

        //路径思路是：顺着终点方向，找到它的父亲...，如此依次回溯，就能找到一条最佳路径了。
        private int pathLength(Node cur) {
            if (cur == null) return 0;

            int step = 1;
            while (cur.parent != null) {//cur.parent !=null ,而不是 cur != null.
                cur = cur.parent;
                step++;
            }
            return step;
        }

        //启发式函数，使用两点距离坐标公式。没有用绝对值。
        //使用的是 毕达哥拉斯 三角函数举例
        public double distance(int x, int y, int targetX, int targetY) {
            return Math.abs(targetX - x + targetY - y);
            //return Math.sqrt(Math.pow(targetX - x, 2) + Math.pow(targetY - y, 2));
        }


        //BFS outtime
        public int shortestPathBinaryMatrixBFS(int[][] grid) {
            if (grid == null) return -1;

            //思路：
            //最短路径，层遍历 BFS
            int len = grid.length;
            if (grid[0][0] == 1 || grid[len - 1][len - 1] == 1) return -1;
            if (len <= 2) return len;//jian zhi

            boolean[][] visited = new boolean[len][len];

            Deque<Node> deque = new LinkedList<>();
            deque.offer(new Node(0, 0));
            int step = 0;
            while (!deque.isEmpty()) {
                int rowSize = deque.size();
                for (int i = 0; i < rowSize; i++) {
                    Node poll = deque.poll();

                    if (poll.x == len - 1 && poll.y == len - 1) {
                        return step + 1;
                    }
                    visited[poll.y][poll.x] = true;

                    for (int j = 0; j < dx.length; j++) {
                        if (valid(poll.x + dx[j], poll.y + dy[j], len, grid, visited)) {

                            deque.offer(new Node(poll.x + dx[j], poll.y + dy[j]));
                        }
                    }
                }
                step++;
            }
            return -1;
        }

        private boolean valid(int x, int y, int len, int[][] grid, boolean[][] visited) {
            return x >= 0 && x < len && y >= 0 && y < len && !visited[y][x] && grid[y][x] != 1;
        }


        class Node {
            int x, y;
            Node parent;
            double cost;

            public Node(int x, int y) {
                this.x = x;
                this.y = y;
            }

            public Node(int x, int y, Node parent, double cost) {
                this.x = x;
                this.y = y;
                this.parent = parent;
                this.cost = cost;
            }

            @Override
            public boolean equals(Object o) {
                if (this == o) return true;
                if (o == null || getClass() != o.getClass()) return false;
                Node node = (Node) o;
                return x == node.x && y == node.y;
            }

            @Override
            public int hashCode() {
                return Objects.hash(x, y);
            }
        }
    }
//leetcode submit region end(Prohibit modification and deletion)

}